package com.lw.leetcode.binary;

/**
 * 154. 寻找旋转排序数组中的最小值 II
 *
 * @Author liw
 * @Date 2021/5/10 10:39
 * @Version 1.0
 */
public class FindMin {

    public static void main(String[] args) {
        int[] arr = {2,2,2,0,1};
        FindMin test = new FindMin();
        int min = test.findMin(arr);
        System.out.println(min);
    }

    public int findMin(int[] nums) {
        int st = 0;
        int end = nums.length - 1;
        while (st < end) {
            int last = nums[end];
            int m = st + ((end - st) >>> 1);
            if (nums[m] > last) {
                st = m + 1;
            } else if (nums[m] < last) {
                end = m;
            } else {
                end--;
            }
        }
        return nums[st];
    }

    /**
     * 剑指 Offer 11. 旋转数组的最小数字
     * @param numbers
     * @return
     */
    public int minArray(int[] numbers) {
        int st = 0;
        int end = numbers.length - 1;
        while (st < end) {
            int last = numbers[end];
            int m = st + ((end - st) >>> 1);
            if (numbers[m] > last) {
                st = m + 1;
            } else if (numbers[m] < last) {
                end = m;
            } else {
                end--;
            }
        }
        if (numbers[0] == numbers[st]) {
            return 0;
        }
        return numbers[st];
    }
}
